#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

const ll maxn{ll(1e6+5)};
ll t,n,m,ind[maxn];
vector<vector<pair<ll,ll>>> adj{maxn};

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
    cin>>t;
    while(t--){
        
        cin>>n>>m;
        fill(ind,ind+n+1,0);
        for(ll i{1};i<=n;i++)adj[i].clear();
        for(ll i{1};i<=m;i++){
            ll u,v,w;
            cin>>u>>v>>w;
            for(ll i{1};i<=n;i++){
                adj[(u+i)%n+1].emplace_back((v+i)%n+1,w);
                adj[(v+i)%n+1].emplace_back((u+i)%n+1,w);
            }
        }
    }
}